package java;

public class Question21 {
    public static void main(String[] args) {

    }
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null){
            if (l2 == null){
                return null;
            }else {
                return l2;
            }
        }else {
            if (l2 == null){
                return l1;
            }
        }
        ListNode current1 = l1;
        ListNode current2 = l2;
        ListNode head;
        ListNode current;
        if (l2.val < l1.val){
            head = l2;
            current = l2;
            current2 = current2.next;
        }else {
            head = l1;
            current = l1;
            current1 = current1.next;
        }
        while (current1 != null && current2 != null){
            if (current1.val <= current2.val){
                current.next = current1;
                current1 = current1.next;
            }else {
                current.next = current2;
                current2 = current2.next;
            }
            current = current.next;
        }
        if (current1 != null){
            current.next = current1;
        }else {
            current.next = current2;
        }
        return head;
    }
}
